#include "graph_support/TestGraphTraversal.h"

#include <iostream>
#include <sstream>

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"

#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/alg/traversal/GrTraversalBFS.h"
#include "graph_support/alg/traversal/GrTraversalDFS.h"

using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::alg::traversal;

namespace
{

void storeEdgesText( VectorGraphTmpl< int >::GrEdgePtr walkEdge, std::ostream & stream )
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;

	GrVertex beg = walkEdge->beg();
	GrVertex end = walkEdge->end();

	stream << "E[ " << beg << " -> " << end << " ]; ";
}

bool oddEdgesFilter( VectorGraphTmpl< int >::GrEdgePtr walkEdge )
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;

	GrVertex b = walkEdge->beg();
	GrVertex e = walkEdge->end();

	return ( b + e ) % 2 == 1 && ( b != 5 || e != 6 );
}

}

void TestGraphBFS()
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;

	std::vector< GrVertex > vertices( 10 );
	for ( int i = 0; i < vertices.size(); i++ )
	{
		vertices[i] = i;
	}

	Graph gr( vertices );

	gr.addEdge( 0, 1 );
	gr.addEdge( 0, 2 );
	gr.addEdge( 0, 3 );
	gr.addEdge( 1, 4 );
	gr.addEdge( 4, 5 );
	gr.addEdge( 5, 6 );
	gr.addEdge( 5, 7 );
	gr.addEdge( 5, 8 );
	gr.addEdge( 6, 9 );

	// TODO 9 [big task, for perspective] virtual graph and algorithms access
//	std::auto_ptr< IGraphTraversalAlgorithm< Graph > > travAlgPtr(
//			new BFSGraphTraversalAlgorithm< Graph >() );
//	IGraphTraversalAlgorithm< Graph > & travAlg = * travAlg;

	{
	std::stringstream buf;
	BOOST_CHECKPOINT( "pre - GrTraversalBFS" );
	GrTraversalBFSAllEdges( gr, 0, boost::bind( storeEdgesText, _1, boost::ref( buf ) ) );
	BOOST_CHECK_EQUAL( std::string(
			"E[ 0 -> 1 ]; E[ 0 -> 2 ]; E[ 0 -> 3 ]; " ) +
			"E[ 1 -> 4 ]; E[ 4 -> 5 ]; E[ 5 -> 6 ]; " +
			"E[ 5 -> 7 ]; E[ 5 -> 8 ]; E[ 6 -> 9 ]; ",
			buf.str() );
	}

	{
	std::stringstream buf;
	GrTraversalBFS( gr, 0, boost::bind( storeEdgesText, _1, boost::ref( buf ) ), & oddEdgesFilter );
	BOOST_CHECK_EQUAL( std::string(
			"E[ 0 -> 1 ]; E[ 0 -> 3 ]; " ) +
			"E[ 1 -> 4 ]; E[ 4 -> 5 ]; " +
			"E[ 5 -> 8 ]; ",
			buf.str() );
	}
}

void TestGraphBFSDuplicateVertices()
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;

	std::vector< GrVertex > vertices( 10 );
	for ( int i = 0; i < vertices.size(); i++ )
	{
		vertices[i] = i;
	}

	Graph gr( vertices );

	gr.addEdge( 0, 1 );
	gr.addEdge( 0, 2 );
	gr.addEdge( 0, 3 );
	gr.addEdge( 1, 4 );
	gr.addEdge( 2, 4 );
	gr.addEdge( 3, 4 );
	gr.addEdge( 4, 5 );

	std::stringstream buf;
	GrTraversalBFSAllEdges( gr, 0, boost::bind( storeEdgesText, _1, boost::ref( buf ) ) );
	BOOST_CHECK_EQUAL( std::string(
			"E[ 0 -> 1 ]; E[ 0 -> 2 ]; E[ 0 -> 3 ]; " ) +
			"E[ 1 -> 4 ]; " +
			"E[ 4 -> 5 ]; ",
			buf.str() );
}

void TestGraphDFS()
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;

	std::vector< GrVertex > vertices( 10 );
	for ( int i = 0; i < vertices.size(); i++ )
	{
		vertices[i] = i;
	}

	Graph gr( vertices );

	gr.addEdge( 0, 1 );
	gr.addEdge( 0, 2 );
	gr.addEdge( 0, 3 );
	gr.addEdge( 1, 4 );
	gr.addEdge( 4, 5 );
	gr.addEdge( 5, 6 );
	gr.addEdge( 5, 7 );
	gr.addEdge( 5, 8 );
	gr.addEdge( 6, 9 );

	{
	std::stringstream buf;
	BOOST_CHECKPOINT( "pre - GrTraversalBFS" );
	GrTraversalDFSAllEdges( gr, 0, boost::bind( storeEdgesText, _1, boost::ref( buf ) ) );
	BOOST_CHECK_EQUAL( std::string(
			"E[ 0 -> 1 ]; E[ 1 -> 4 ]; E[ 4 -> 5 ]; E[ 5 -> 6 ]; E[ 6 -> 9 ]; " ) +
			"E[ 5 -> 7 ]; E[ 5 -> 8 ]; " +
			"E[ 0 -> 2 ]; " +
			"E[ 0 -> 3 ]; ",
			buf.str() );
	}

	{
	std::stringstream buf;
	GrTraversalDFS( gr, 0, boost::bind( storeEdgesText, _1, boost::ref( buf ) ), & oddEdgesFilter );
	BOOST_CHECK_EQUAL( std::string(
			"E[ 0 -> 1 ]; E[ 1 -> 4 ]; E[ 4 -> 5 ]; E[ 5 -> 8 ]; " ) +
			"E[ 0 -> 3 ]; ",
			buf.str() );
	}
}
